from functools import cache


class Solution:
    def waysToReachStair(self, k: int) -> int:
        tot = 0

        @cache
        def f(start, jump, down):
            if start > k + 1:
                return 0
            ans = start == k
            if down == 1 and start > 0:
                ans += f(start - 1, jump, 0)
            ans += f(start + pow(2, jump), jump + 1, 1)
            return ans

        return f(1, 0, 1)


s = Solution()
print(s.waysToReachStair(1000000000))
